- deterministic and nondeterministic polynomial space
- Программирование: детерминированное и недетерминированное полиномиальное пространство
Универсальный англо-русский словарь. Академик.ру. 2011.
deterministic and nondeterministic polynomial space
Смотреть что такое "deterministic and nondeterministic polynomial space" в других словарях:
Polynomial space — In computational complexity theory, polynomial space refers to the space required in computation of a problem where the space, m ( n ), is no greater than a polynomial function of the problem size, n .Written mathematically, m ( n ) = O( n k )… … Wikipedia
Space hierarchy theorem — In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. For… … Wikipedia
Deterministic context-free language — A deterministic context free language is a formal language which is defined by a deterministic context free grammar.[1] The set of deterministic context free languages is called DCFL[2] and is identical to the set of languages accepted by a… … Wikipedia
List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… … Wikipedia
List of computing and IT abbreviations — This is a list of computing and IT acronyms and abbreviations. Contents: 0–9 A B C D E F G H I J K L M N O P Q R S T U V W X Y … Wikipedia
List of computability and complexity topics — This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard… … Wikipedia
NP (complexity) — Diagram of complexity classes provided that P ≠ NP. The existence of problems outside both P and NP complete in this case was established by Ladner.[1] In computational complexity theory, NP is one of the most fundamental complexity classes. The… … Wikipedia
NL (complexity) — In computational complexity theory, NL (Nondeterministic Logarithmic space) is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. NL is a… … Wikipedia
Список терминов, относящихся к алгоритмам и структурам данных — Это служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавливается на информационные списки и глоссарии … Википедия
Список терминов — Список терминов, относящихся к алгоритмам и структурам данных Это сл … Википедия
Complexity class — In computational complexity theory, a complexity class is a set of problems of related resource based complexity. A typical complexity class has a definition of the form: the set of problems that can be solved by an abstract machine M using… … Wikipedia
